<html>
  <head>
    <meta charset="utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1" />
<title> 十大经典排序算法 | 清汤牛肉锅</title>
<meta name="description" content="温故而知新
" />
<link rel="shortcut icon" href="https://ArtZoick.github.io//favicon.ico?v=1572228390311">
<link rel="stylesheet" href="https://use.fontawesome.com/releases/v5.7.2/css/all.css" integrity="sha384-fnmOCqbTlWIlj8LyTjo7mOUStjsKC4pOpQbqyi7RrhN7udi9RwhKkMHpvLbHG9Sr" crossorigin="anonymous">
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.10.0/katex.min.css">
<link rel="stylesheet" href="https://ArtZoick.github.io//styles/main.css">

<script src="https://cdn.bootcss.com/highlight.js/9.12.0/highlight.min.js"></script>
<link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Droid+Serif:400,700">


<script async src="https://www.googletagmanager.com/gtag/js?id=UA-143265163-1"></script>
<script>
  window.dataLayer = window.dataLayer || [];
  function gtag(){dataLayer.push(arguments);}
  gtag('js', new Date());

  gtag('config', 'UA-143265163-1');
</script>


  </head>
  <body>
    <div class="main">
      <div class="main-content">
        <div class="site-header">
  <a href="https://ArtZoick.github.io/">
  <img class="avatar" src="https://ArtZoick.github.io//images/avatar.png?v=1572228390311" alt="">
  </a>
  <h1 class="site-title">
    清汤牛肉锅
  </h1>
  <p class="site-description">
    温故而知新

  </p>
  <div class="menu-container">
    
      
        <a href="/" class="menu">
          首页
        </a>
      
    
      
        <a href="/archives" class="menu">
          归档
        </a>
      
    
      
        <a href="/tags" class="menu">
          标签
        </a>
      
    
      
        <a href="/post/about" class="menu">
          关于
        </a>
      
    
      
        <a href="/post/beef" class="menu">
          牛肉锅
        </a>
      
    
  </div>
  <div class="social-container">
    
      
    
      
    
      
    
      
    
      
    
  </div>
</div>

        <div class="post-detail">
          <article class="post">
            <h2 class="post-title">
               十大经典排序算法
            </h2>
            <div class="post-info">
              <span>
                2019-09-25
              </span>
              <span>
                12 min read
              </span>
              
                <a href="https://ArtZoick.github.io//tag/数据结构与算法" class="post-tag">
                  # 数据结构与算法
                </a>
              
            </div>
            
            <div class="post-content-wrapper">
              <div class="post-content">
                <p>参考：<a href="https://www.jianshu.com/p/47170b1ced23">一文搞定十大经典排序算法（Java实现）</a><br>
<a href="%5Bhttps://blog.csdn.net/wq_1995/article/details/81937926#6%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8Fquick-sort%5D(https://blog.csdn.net/wq_1995/article/details/81937926#6%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8Fquick-sort)">十大经典排序算法总结（Java语言实现）</a></p>
<h2 id="一-算法的分类">一、算法的分类</h2>
<h3 id="1-概念">1、概念</h3>
<p>将杂乱无章的数据元素，通过一定的方法按关键字顺序排列的过程叫做排序。</p>
<h3 id="2-分类">2、分类</h3>
<ul>
<li><strong>非线性时间比较类排序</strong>: 通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此称为非线性时间比较类排序。</li>
<li><strong>线性时间非比较类排序</strong>: 不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。</li>
</ul>
<figure data-type="image" tabindex="1"><img src="https://ArtZoick.github.io//post-images/sort/1.png" alt=""></figure>
<h3 id="3-比较">3、比较</h3>
<figure data-type="image" tabindex="2"><img src="https://ArtZoick.github.io//post-images/sort/2.png" alt=""></figure>
<p>4、相关概念</p>
<ul>
<li>**稳定：**如果a原本在b前面且a=b，排序之后a仍然在b的前面。</li>
<li>**不稳定：**如果a原本在b的前面且a=b，排序之后 a 可能会出现在 b 的后面。</li>
<li>**时间复杂度：**对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。</li>
<li>**空间复杂度：**是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。</li>
<li>**内部排序：**所有排序操作都在内存中完成。本文主要介绍的是内部排序。</li>
<li>**外部排序：**待排序记录的数量很大，以致于内存不能一次容纳全部记录，所以在排序过程中需要对外存进行访问的排序过程。</li>
</ul>
<h2 id="二-各算法原理及实现">二、各算法原理及实现</h2>
<p>下面我们来逐一分析十大经典排序算法，主要围绕下列问题展开：<br>
1、算法的基本思想是什么？<br>
2、算法的代码实现？<br>
3、算法的时间复杂度是多少？（平均、最好、最坏）什么情况下最好？什么情况下最坏？<br>
4、算法的空间复杂度是多少？<br>
5、算法的稳定性如何？</p>
<h3 id="1-冒泡排序bubble-sort">1、冒泡排序（Bubble Sort）</h3>
<p><strong>① 基本思想</strong><br>
冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为每趟比较将当前数列未排序部分的最大的元素“沉”到数列末端，而小的元素会经由交换慢慢“浮”到数列的顶端。</p>
<p><strong>② 算法描述</strong><br>
1）比较相邻的元素。如果前一个比后一个大，就交换它们两个；<br>
2）对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；<br>
3）针对所有的元素重复以上的步骤，除了最后一个；<br>
4）重复步骤1~3，直到排序完成。为了优化算法，可以设立一个布尔标识，每趟排序开始前设为false，如果该趟排序发生了交换就置为true，如果一趟排序结束标识仍为false表示该趟排序没有发生交换，即数组已经有序，可以提前结束排序。</p>
<p><strong>③ 动图演示</strong></p>
<img src="file://C:/Users/zoick/OneDrive/Gridea/post-images/sort/1.gif"  />
<p><strong>④ 代码实现</strong></p>
<pre><code class="language-java">public static int[] bubbleSort(int[] array) {
    int count = 0;
    if (array.length == 0) {
        return array;
    }
    for (int i = 0; i &lt; array.length - 1; i++) {  //外层循环一次为一趟排序
              /*设置标识，判断这趟排序是否发生了交换。
             如果未发生交换，则说明数组已经有序，不必再排序了*/
        boolean isSwap = false;
        for (int j = 0; j &lt; array.length - 1 - i; j++) { //内层循环一次为一次相邻比较
            if (array[j + 1] &lt; array[j]) {
                int temp = array[j + 1];
                array[j + 1] = array[j];
                array[j] = temp;
                isSwap = true;
                count++;
            }
        }
        if (!isSwap) {
            break;
        }
    }
    return array;
}
</code></pre>
<p><strong>⑤ 时间复杂度</strong><br>
冒泡排序平均时间复杂度为O(n2)，最好时间复杂度为O(n)，最坏时间复杂度为O(n2)。<br>
**最好情况：**如果待排序元素本来是正序的，那么一趟冒泡排序就可以完成排序工作，比较和移动元素的次数分别是 (n - 1) 和 0，因此最好情况的时间复杂度为O(n)。<br>
**最坏情况：**如果待排序元素本来是逆序的，需要进行 (n - 1) 趟排序，所需比较和移动次数分别为 n * (n - 1) / 2和 3 * n * (n-1) / 2。因此最坏情况下的时间复杂度为O(n2)。</p>
<p><strong>⑥ 空间复杂度</strong><br>
冒泡排序使用了常数空间，空间复杂度为O(1)</p>
<p><strong>⑦ 稳定性</strong><br>
当 array[j] == array[j+1] 的时候，我们不交换 array[i] 和 array[j]，所以冒泡排序是稳定的。</p>
<p><strong>⑧ 算法拓展</strong><br>
**鸡尾酒排序，又称定向冒泡排序、搅拌排序等，是对冒泡排序的改进。**在把最大的数往后面冒泡的同时，把最小的数也往前面冒泡，同时收缩无序区的左右边界，有序区在序列左右逐渐累积。</p>
<p>动图如下：</p>
<img src="file://C:/Users/zoick/OneDrive/Gridea/post-images/sort/1.1.gif"  />
<p>代码如下：</p>
<pre><code class="language-java">public static void cocktailSort(int[] array) {
        int left = 0,right = array.length-1;
        while(left &lt; right) {
            for(int i = left; i &lt; right; i++) 
              if(array[i] &gt; array[i+1]) 
                    swap(array,i,i + 1);
            right--;
            for(int i = right; i &gt; left; i--) 
              if(array[i] &lt; array[i-1]) 
                    swap(array,i,i-1);
            left++;
        }
}
</code></pre>
<p>鸡尾酒排序是稳定的。它的平均时间复杂度为O(n2)，最好情况是待排序列原先就是正序的，时间复杂度为O(n)，最坏情况是待排序列原先是逆序的，时间复杂度为O(n2)。空间复杂度为O(1)。</p>
<h3 id="2-选择排序selection-sort">2、选择排序（Selection Sort）</h3>
<p>**①、基本思想：**选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。</p>
<p><strong>②、算法描述：（<strong>n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。</strong>）</strong></p>
<ul>
<li>初始状态：无序区为R[1..n]，有序区为空；</li>
<li>第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；</li>
<li>n-1趟结束，数组有序化了。</li>
</ul>
<p><strong>③、动图演示</strong></p>
<figure data-type="image" tabindex="3"><img src="https://ArtZoick.github.io//post-images/sort/2.gif" alt=""></figure>
<p><strong>④ 代码实现</strong></p>
<pre><code class="language-java">public static int[] selectionSort(int[] array) {
    if (array.length == 0) {
        return array;
    }
    for (int i = 0; i &lt; array.length; i++) {
        int minIndex = i;
        for (int j = i; j &lt; array.length; j++) {
            if (array[j] &lt; array[minIndex]) { //找到最小的数
                minIndex = j; //将最小数的索引保存
            }
        }
        int temp = array[minIndex]; //将最小数和无序区的第一个数交换
        array[minIndex] = array[i];
        array[i] = temp;
    }
    return array;
}
</code></pre>
<p><strong>⑤ 时间复杂度</strong></p>
<p>简单选择排序平均时间复杂度为O(n<sup>2</sup>)，最好时间复杂度为O(n<sup>2</sup>)，最坏时间复杂度为O(n<sup>2</sup>)。<br>
**最好情况：**如果待排序元素本来是正序的，则移动元素次数为 0，但需要进行 n * (n - 1) / 2 次比较。<br>
**最坏情况：**如果待排序元素中第一个元素最大，其余元素从小到大排列，则仍然需要进行 n * (n - 1) / 2 次比较，且每趟排序都需要移动 3 次元素，即移动元素的次数为3 * (n - 1)次。<br>
<strong>需要注意的是，简单选择排序过程中需要进行的比较次数与初始状态下待排序元素的排列情况无关。</strong></p>
<p><strong>⑥ 空间复杂度</strong><br>
简单选择排序使用了常数空间，空间复杂度为O(1)</p>
<p><strong>⑦ 稳定性</strong><br>
简单选择排序不稳定，比如序列 2、4、2、1，我们知道第一趟排序第 1 个元素 2 会和 1 交换，那么原序列中 2 个 2 的相对前后顺序就被破坏了，所以简单选择排序不是一个稳定的排序算法。</p>
<h3 id="3-直接插入排序insertion-sort">3、直接插入排序（Insertion Sort）</h3>
<p><strong>① 基本思想</strong><br>
直接插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。</p>
<p><strong>② 算法描述</strong></p>
<p>一般来说，直接插入排序都采用in-place（原地算法）在数组上实现。具体算法描述如下：<br>
1）从第一个元素开始，该元素可以认为已经被排序；<br>
2）取出下一个元素，在已经排序的元素序列中从后向前扫描；<br>
3）如果该元素（已排序）大于新元素，将该元素移到下一位置；<br>
4）重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；<br>
5）将新元素插入到该位置后；<br>
6）重复步骤2~5。</p>
<p><strong>③ 动图演示</strong></p>
<figure data-type="image" tabindex="4"><img src="https://ArtZoick.github.io//post-images/sort/3.gif" alt=""></figure>
<p><strong>④ 代码实现</strong></p>
<pre><code class="language-java">public static int[] insertionSort(int[] array) {
    if (array.length == 0) {
        return array;
    }
    int current;
    for (int i = 1; i &lt; array.length; i++) {
        current = array[i]; //这次比较的数先存如current
        int preIndex = i - 1; //前一个数的索引
        while (preIndex &gt;= 0 &amp;&amp; current &lt; array[preIndex]) { //当前一个数比现在的数还大则执行while里的内容，同时 要保证索引大于0
            array[preIndex + 1] = array[preIndex]; 
            preIndex--;
        }
        array[preIndex + 1] = current;
    }
    return array;
}
</code></pre>
<p><strong>⑤ 时间复杂度</strong><br>
直接插入排序平均时间复杂度为O(n<sup>2</sup>)，最好时间复杂度为O(n)，最坏时间复杂度为O(n<sup>2</sup>)。<br>
**最好情况：**如果待排序元素本来是正序的，比较和移动元素的次数分别是 (n - 1) 和 0，因此最好情况的时间复杂度为O(n)。<br>
**最坏情况：**如果待排序元素本来是逆序的，需要进行 (n - 1) 趟排序，所需比较和移动次数分别为 n * (n - 1) / 2和 n * (n - 1) / 2。因此最坏情况下的时间复杂度为O(n<sup>2</sup>)。</p>
<p><strong>⑥ 空间复杂度</strong><br>
直接插入排序使用了常数空间，空间复杂度为O(1)</p>
<p><strong>⑦ 稳定性</strong><br>
直接插入排序是稳定的。</p>
<p><strong>⑧ 算法拓展</strong><br>
在直接插入排序中，待插入的元素总是在有序区线性查找合适的插入位置，没有利用有序的优势，考虑使用二分查找搜索插入位置进行优化，即<strong>二分插入排序</strong>。</p>
<p>代码实现如下：</p>
<pre><code class="language-java">public static int[] BinaryInsertionSort(int[] array) {
        if (array.length == 0)
            return array;
        for(int i = 1;i &lt; array.length;i++) {
            int left = 0;
            int right = i - 1;  // left 和 right 分别为有序区的左右边界 
            int current = array[i];
            while (left &lt;= right) {
           //搜索有序区中第一个大于 current 的位置，即为 current 要插入的位置
                int mid = left + ((right - left) &gt;&gt; 1);
                if(array[mid] &gt; current){
                    right = mid - 1;
                }else{
                    left = mid + 1;
                }
            }
            for(int j = i - 1;j &gt;= left;j--) {
                array[j + 1] = array[j];
            }
            array[left] = current; // left 为第一个大于 current 的位置，插入 current
        }
        return array;
 }
</code></pre>
<p>二分插入排序是稳定的。它的平均时间复杂度是O(n2)，最好时间复杂度为O(nlogn)，最坏时间复杂度为O(n2)。</p>

              </div>
              <div class="toc-container">
                <ul class="markdownIt-TOC">
<li>
<ul>
<li><a href="#%E4%B8%80-%E7%AE%97%E6%B3%95%E7%9A%84%E5%88%86%E7%B1%BB">一、算法的分类</a>
<ul>
<li><a href="#1-%E6%A6%82%E5%BF%B5">1、概念</a></li>
<li><a href="#2-%E5%88%86%E7%B1%BB">2、分类</a></li>
<li><a href="#3-%E6%AF%94%E8%BE%83">3、比较</a></li>
</ul>
</li>
<li><a href="#%E4%BA%8C-%E5%90%84%E7%AE%97%E6%B3%95%E5%8E%9F%E7%90%86%E5%8F%8A%E5%AE%9E%E7%8E%B0">二、各算法原理及实现</a>
<ul>
<li><a href="#1-%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8Fbubble-sort">1、冒泡排序（Bubble Sort）</a></li>
<li><a href="#2-%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8Fselection-sort">2、选择排序（Selection Sort）</a></li>
<li><a href="#3-%E7%9B%B4%E6%8E%A5%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8Finsertion-sort">3、直接插入排序（Insertion Sort）</a></li>
</ul>
</li>
</ul>
</li>
</ul>

              </div>
            </div>
          </article>
        </div>

        
          <div class="next-post">
            <div class="next">下一篇</div>
            <a href="https://ArtZoick.github.io//post/spring_4">
              <h3 class="post-title">
                Spring_4 JdbcTemplate、事务控制
              </h3>
            </a>
          </div>
        

        
          
            <link rel="stylesheet" href="https://unpkg.com/gitalk/dist/gitalk.css">
<script src="https://unpkg.com/gitalk/dist/gitalk.min.js"></script>

<div id="gitalk-container"></div>

<script>

  var gitalk = new Gitalk({
    clientID: 'a2471d09bddb5be481ee',
    clientSecret: '05d427fb27f873cfabace27b9f042f2c7f23000f',
    repo: 'ArtZoick.github.io',
    owner: 'ArtZoick',
    admin: ['ArtZoick'],
    id: (location.pathname).substring(0, 49),      // Ensure uniqueness and length less than 50
    distractionFreeMode: false  // Facebook-like distraction free mode
  })

  gitalk.render('gitalk-container')

</script>

          

          
        

        <div class="site-footer">
  <a href="https://zhidao.baidu.com/question/1867120235416383707.html" target="_blank" onclick="alert('盲生，你发现了华点！');">学习强国</a>

<!--Tido对话插件-->
<script src="//code.tidio.co/5fh6jaqvluqj8jjuf5zlqrf5tlzpktnx.js"></script>
<style>
.text-popup {
    animation: textPopup 1s;
    color: red;
    user-select: none;
    white-space: nowrap;
    position: absolute;
    z-index: 99;
}
@keyframes textPopup {
    0%, 100% {
        opacity: 0;
    }
    5% {
        opacity: 1;
    }
    100% {
        transform: translateY(-50px);    
    }
}
</style>
<script type="text/javascript" src="https://cdn.bootcss.com/canvas-nest.js/1.0.1/canvas-nest.min.js">
!function(){function n(n,e,t){return n.getAttribute(e)||t}function e(n){return document.getElementsByTagName(n)}
function t(){var t=e("script"),o=t.length,i=t[o-1];return{l:o,z:n(i,"zIndex",-1),o:n(i,"opacity",.5),c:n(i,"color","0,0,0")
,n:n(i,"count",99)}}function o(){a=m.width=window.innerWidth||document.documentElement.clientWidth||document.body.clientWidt
h,c=m.height=window.innerHeight||document.documentElement.clientHeight||document.body.clientHeight}function i(){r.clearRect
(0,0,a,c);var n,e,t,o,m,l;s.forEach(function(i,x){for(i.x+=i.xa,i.y+=i.ya,i.xa*=i.x>a||i.x<0?-1:1,i.ya*=i.y>c||i.y<0?-1:1,r.
fillRect(i.x-.5,i.y-.5,1,1),e=x+1;e<u.length;e++)n=u[e],null!==n.x&&null!==n.y&&(o=i.x-n.x,m=i.y-n.y,l=o*o+m*m,l<n.max&&(n===
y&&l>=n.max/2&&(i.x-=.03*o,i.y-=.03*m),t=(n.max-l)/n.max,r.beginPath(),r.lineWidth=t/2,r.strokeStyle="rgba("+d.c+","+(t+.2)+")
",r.moveTo(i.x,i.y),r.lineTo(n.x,n.y),r.stroke()))}),x(i)}var a,c,u,m=document.createElement("canvas"),d=t(),l="c_n"+d.l,r=m.
getContext("2d"),x=window.requestAnimationFrame||window.webkitRequestAnimationFrame||window.mozRequestAnimationFrame||window.
oRequestAnimationFrame||window.msRequestAnimationFrame||function(n){window.setTimeout(n,1e3/45)},w=Math.random,y={x:null,y:nul
l,max:2e4};m.id=l,m.style.cssText="position:fixed;top:0;left:0;z-index:"+d.z+";opacity:"+d.o,e("body")[0].appendChild(m),o(),
window.οnresize=o,window.οnmοusemοve=function(n){n=n||window.event,y.x=n.clientX,y.y=n.clientY},window.οnmοuseοut=function(){y
.x=null,y.y=null};for(var s=[],f=0;d.n>f;f++){var h=w()*a,g=w()*c,v=2*w()-1,p=2*w()-1;s.push({x:h,y:g,xa:v,ya:p,max:6e3})}u=
s.concat([y]),setTimeout(function(){i()},100)}();
</script>

<!--鼠标点击-->
<!--富强-->
<script type="text/javascript"> 
/* 鼠标特效 */ 
var a_idx = 0; 
jQuery(document).ready(function($) { 
    $("body").click(function(e) { 
        var a = new Array("富强", "民主", "文明", "和谐", "自由", "平等", "公正" ,"法治", "爱国", "敬业", "诚信", "友善"); 
        var $i = $("<span/>").text(a[a_idx]); 
        a_idx = (a_idx + 1) % a.length; 
        var x = e.pageX, 
        y = e.pageY; 
        $i.css({ 
            "z-index": 999, 
            "top": y - 20, 
            "left": x, 
            "position": "absolute", 
            "font-weight": "bold", 
            "color": "#ff6651" 
        }); 
        $("body").append($i); 
        $i.animate({ 
            "top": y - 180, 
            "opacity": 0 
        }, 
        1500, 
        function() { 
            $i.remove(); 
        }); 
    }); 
}); 
</script>
<!--edn--富强--> | 
  <a class="rss" href="https://ArtZoick.github.io//atom.xml" target="_blank">RSS</a>
</div>

<script>
  hljs.initHighlightingOnLoad()

  let mainNavLinks = document.querySelectorAll(".markdownIt-TOC a");

  // This should probably be throttled.
  // Especially because it triggers during smooth scrolling.
  // https://lodash.com/docs/4.17.10#throttle
  // You could do like...
  // window.addEventListener("scroll", () => {
  //    _.throttle(doThatStuff, 100);
  // });
  // Only not doing it here to keep this Pen dependency-free.

  window.addEventListener("scroll", event => {
    let fromTop = window.scrollY;

    mainNavLinks.forEach((link, index) => {
      let section = document.getElementById(decodeURI(link.hash).substring(1));
      let nextSection = null
      if (mainNavLinks[index + 1]) {
        nextSection = document.getElementById(decodeURI(mainNavLinks[index + 1].hash).substring(1));
      }
      console.log('section.offsetHeight', section.offsetHeight);
      if (section.offsetTop <= fromTop) {
        if (nextSection) {
          if (nextSection.offsetTop > fromTop) {
            link.classList.add("current");
          } else {
            link.classList.remove("current");    
          }
        } else {
          link.classList.add("current");
        }
      } else {
        link.classList.remove("current");
      }
    });
  });

</script>

      </div>
    </div>
  </body>
</html>
